package com.datastructure.test.findunsortedsubarray;

import java.util.Arrays;

public class FindUnsortedSubarray {

    public static void main(String[] args) {
        FindUnsortedSubarray findUnsortedSubarray = new FindUnsortedSubarray();
        int[] nums = {1,2,3,4};
        int unsortedSubarray = findUnsortedSubarray.findUnsortedSubarray(nums);
        System.out.println(unsortedSubarray);
    }

    public int findUnsortedSubarray (int[] nums) {
        // write code here
        if(nums==null||nums.length==0){
            return 0;
        }
        int length = nums.length;
        int[] temp = new int[length];
        System.arraycopy(nums,0,temp,0,length);
        Arrays.sort(temp);
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(temp[i]!=nums[i]){
                index=i;
                break;
            }else {
                index=i;
            }
        }
        if(index==length-1){
            return 0;
        }
        int left = 0;
        int right = length-1;
        for (int i = 0; i < nums.length; i++) {
            if(temp[i]!=nums[i]){
                left=i;
                break;
            }else {
                left=i;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if(temp[i]!=nums[i]){
                right=i;
                break;
            }
        }
        return right-left+1;
    }

    public void quickSort(int[] arrays, int low, int hi) {

        if (low < hi) {
            // 求每次分治的分割线
            int divideIndex = getDivideIndex(arrays, low, hi);
            // 再递归分别对分割的俩个子数组进行递归排序
            quickSort(arrays, low, divideIndex - 1);
            quickSort(arrays, divideIndex + 1, hi);
        }
    }

    public int getDivideIndex(int[] arrays, int low, int hi) {
        int baseValue = arrays[low];
        int oldLow = low;
        while (low < hi) {
            while (low < hi && arrays[hi] >= baseValue) {
                hi--;
            }
            while (low < hi && arrays[low] <= baseValue) {
                low++;
            }
            if (low < hi) {
                swap(arrays, low, hi);
            }
        }
        if (low == hi) {
            arrays[oldLow] = arrays[low];
            arrays[low] = baseValue;
        }
        return low;
    }

    public void swap(int[] arrays, int low, int high) {
        int temp = 0;
        temp = arrays[low];
        arrays[low] = arrays[high];
        arrays[high] = temp;
    }

}
